package JavaCode.contest.weekly.n0_200.n141;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class N2 {

    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        Map<Integer,Integer> map=new HashMap<>();
        PriorityQueue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0]-o1[0];
            }
        });
        for (int i=0;i<values.length;i++)
        {
            queue.add(new int[]{values[i],labels[i]});
        }
        int res=0;
        int cnt=0;
        while (!queue.isEmpty())
        {
            int[] poll = queue.poll();
            if(map.getOrDefault(poll[1],0)==use_limit)continue;
            else
            {
                res+=poll[0];
                map.put(poll[1],map.getOrDefault(poll[1],0)+1);
                cnt++;
                if(cnt==num_wanted)break;
            }
        }
        return res;
    }
}
/**
 *我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。
 *
 * 我们从这些项中选出一个子集 S，这样一来：
 *
 * |S| <= num_wanted
 * 对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。
 * 返回子集 S 的最大可能的 和。
 *
 *
 *
 * 示例 1：
 *
 * 输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
 * 输出：9
 * 解释：选出的子集是第一项，第三项和第五项。
 * 示例 2：
 *
 * 输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
 * 输出：12
 * 解释：选出的子集是第一项，第二项和第三项。
 * 示例 3：
 *
 * 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
 * 输出：16
 * 解释：选出的子集是第一项和第四项。
 * 示例 4：
 *
 * 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
 * 输出：24
 * 解释：选出的子集是第一项，第二项和第四项。
 *
 *
 * 提示：
 *
 * 1 <= values.length == labels.length <= 20000
 * 0 <= values[i], labels[i] <= 20000
 * 1 <= num_wanted, use_limit <= values.length
 */
